/*
 * @lc app=leetcode.cn id=68 lang=typescript
 *
 * [68] 文本左右对齐
 */

// @lc code=start
function fullJustify(words: string[], maxWidth: number): string[] {
  const createBlank = (num: number): string => {
    return ''.padStart(num, ' ');
  };
  const m = words.length;
  const ans: string[] = [];
  // 记录最后访问的words数组下标
  let tail = 0;

  while (1) {
    // 当前行的单词长度之和
    let sum = 0;
    // 当前行第一个单词的数组下标
    let head = tail;
    while (tail < m && sum + words[tail].length + tail - head <= maxWidth) {
      sum += words[tail++].length;
    }

    // 最后一行,单词左对齐，单词之间只有一个空格，其他的填充到尾部
    if (tail === m) {
      let str = words.slice(head).join(' ');
      str = str.padEnd(maxWidth, ' ');
      ans.push(str);
      break;
    }

    // 当前行只有一个单词，单词左对齐，尾部填充空格
    const wordCount = tail - head;
    if (wordCount === 1) {
      let str = words[head];
      str = str.padEnd(maxWidth, ' ');
      ans.push(str);
      continue;
    }

    // 普通情况
    const blankCount = maxWidth - sum;
    const avgBlank = (blankCount / (wordCount - 1)) >> 0;
    const extrBlank = blankCount % (wordCount - 1);
    const s1 = words.slice(head, head + extrBlank + 1).join(createBlank(avgBlank + 1));
    const s2 = words.slice(head + extrBlank + 1, tail).join(createBlank(avgBlank));
    ans.push(s1 + createBlank(avgBlank) + s2);
  }

  return ans;
}
// @lc code=end
